This invention relates to a system for implementing microprogrammed control in a very high speed computer. More particularly, this invention relates to a microcode sequencing technique (for example, conditional branching) done in such a way as to maximize the pipeline execution rate. The computer described is presumed to be a pipeline structure in which a single phase clocking system is used to clock the pipeline. The instruction execution rate is proportional to the clocking rate, thus minimizing the clock cycle time which is critical to achieving maximum performance. The computer utilizes microprogrammed control, thus one of the pipeline segments consists of the microcode control store. A microcode control store is the memory used to store the microinstructions. A microinstruction is the contents of a single control store address and contains the bits used for control. The hardware design must be capable of accessing one microinstruction per clock. This means that the minimum clock cycle time must be at least as long as the access time of the memory chip plus the input and output pipeline registers. Thus, this invention is a system of implementing a microprogrammed control unit in a pipeline computer in which the clock cycle is the minimum described and the clocking rate is at a maximum rate for any given memory chip.
Prior art implementions of such a memory system all have at least one additional logic level between the various registers in the pipeline. These additional logic levels directly increase the clock cycle time period. A typical example is for some control store bits to be used to control the selection of the control store address at the next clock cycle time. In this example, the clock cycle time is computed as: memory access time plus register delay time plus multiplexer select path delay time. These designs all have a decision interval of one clock. That is, the current microinstruction always knows how to address the next microinstruction. The cost of obtaining the decision time of one is the extra gate levels described.
The present invention does not have a guaranteed decision interval of one clock cycle. In most applications, this invention will perform with a decision interval of one clock. This does not mean however that a decision interval of one clock cycle is guaranteed, since no control store bits feed directly back to select the next data for the control store address register. However, the proposed invention will run most of the time with a decision interval of one clock cycle, the only exception being a wrong prediction on a microcode conditional branch.
The use of the microprogrammed control in the computer is to decode instructions. More specifically, opcodes are received from the instruction register and used to generate the specific control signals that cause the instruction to be executed in the computer. In this invention, the microprogrammed control categorizes instructions received into two classes, single microinstructions and multiple microinstructions. A single instruction is one in which only a single microcode instruction is issued to the machine to cause the instruction to be fully executed. A multiple microcode instruction is one in which more than one microcode instruction must be issued to the machine to cause the instruction to be executed.
Once instructions are brought into the microprogrammed control unit, they execute in one of three ways: (1) single microinstructions, (2) sequential multiple microinstructions, and (3) sequential multiple microinstructions with conditional branching instructions. With respect to microcode sequencing, with case 1, the only sequencing required by a microinstruction is to go to the first microinstruction of the next instruction. In case 2, the only sequencing used between microinstructions is increment. In case 3, many types of sequencing are supported, including increment, conditional branch, subroutine call and return, unconditional branch and repeat.
A system according to this invention will handle cases 1 and 2 with a decision interval equal to one clock cycle, since the design will always do a correct look-ahead. The system will handle all branches of case 3 with a decision interval of one clock cycle if the branch is not taken and a decision interval of 2 if the branch is taken. This is because the hardware makes a look-ahead guess of the next address. When the guess is correct, the decision interval is 1. When the guess is incorrect, the guess is purged and the correct path is resumed with a decision interval of 2.
In computer applications, most of the instruction microcode is classified as case 1 or 2. The small number of case 3 instructions can be handled efficiently if the branch probabilities are known, which is often the case. Practice of the present invention can come very close to total execution with a decision interval of 1 clock cycle without suffering the additional gate delays required to guarantee a decision time of 1 clock cycle interval.